package com.ryujung.dfs_backtracking;

import java.util.*;

class Solution332 {

    /**
     * 思路：
     * 官方的欧拉回路解法
     */
    public List<String> findItinerary(List<List<String>> tickets) {
        List<String> res = new ArrayList<>();
        if (tickets == null) {
            return res;
        }
        HashMap<String, PriorityQueue<String>> map = new HashMap<>();
        for (List<String> ticket : tickets) {
            String src = ticket.get(0);
            String dest = ticket.get(1);
            PriorityQueue<String> que = map.getOrDefault(src, new PriorityQueue<>());
            que.add(dest);
            map.put(src, que);
        }
        dfs(tickets, map, "JFK", res);
        Collections.reverse(res);
        return res;
    }

    private void dfs(List<List<String>> tickets, HashMap<String, PriorityQueue<String>> map, String src, List<String> res) {
        PriorityQueue<String> destQue = map.get(src);
        while (destQue != null && destQue.size() > 0) {
            String dest = destQue.poll();
            dfs(tickets, map, dest, res);
        }
        res.add(src);
    }

    /**
     * itinerary 行程
     * lexical 词汇的
     * <p>
     * 获得信息：
     * 1. List<String>中有两个元素，出发地和目的地
     * 2. List<List<String>> tickets列表中的所有List<String>都需要使用，且不能重复
     * 3. 如果有多个答案，则取字母序列最小的组合
     * 4. 必须要以JFK作为起始位置
     * <p>
     * 思路：
     * 需要将每张ticket进行排列组合，不符合条件的需要回溯，最终获得答案
     * 需要使用回溯算法解决该问题
     * <p>
     * <p>
     * 运行失败:
     * Time Limit Exceeded
     * 复杂度过高
     */
    public List<String> findItinerary00(List<List<String>> tickets) {
        List<List<String>> resCollection = new ArrayList<>();
        Deque<String> ans = new ArrayDeque<>();
        boolean[] isHasUsedArr = new boolean[tickets.size()];
        dfs00(tickets, "JFK", isHasUsedArr, ans, resCollection);
        // TODO 如何解决字典排序的问题？
        // 当结果集中存在多个答案，如何获取其中字典排序最小的List<String>
        resCollection.sort(Comparator.comparing(Object::toString));
        System.out.println(resCollection);
        return resCollection.isEmpty() ? null : resCollection.get(0);
    }

    private void dfs00(List<List<String>> tickets, String curPosition, boolean[] isHasUsedArr,
                       Deque<String> ans, List<List<String>> resCollection) {
        if (ans.size() == tickets.size()) {
            ans.addLast(curPosition);
            resCollection.add(new ArrayList<>(ans));
            ans.removeLast();
            return;
        }

        for (int i = 0; i < tickets.size(); i++) {
            if (!isHasUsedArr[i]) {
                String from = tickets.get(i).get(0);
                if (!curPosition.equals(from)) {
                    continue;
                }

                // 出发地加入结果集
                ans.addLast(from);
                String newDestination = tickets.get(i).get(1);
                isHasUsedArr[i] = true;
                dfs00(tickets, newDestination, isHasUsedArr, ans, resCollection);
                isHasUsedArr[i] = false;
                ans.removeLast();
            }
        }
    }

    /**
     * [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
     */
    public static void main(String[] args) {
        Solution332 s = new Solution332();
        System.out.println(s.findItinerary(Arrays.asList(
                Arrays.asList("MUC", "LHR"),
                Arrays.asList("JFK", "MUC"),
                Arrays.asList("SFO", "SJC"),
                Arrays.asList("LHR", "SFO"))));

        /*
        输入：tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
        输出：["JFK","ATL","JFK","SFO","ATL","SFO"]
        解释：另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"] ，但是它字典排序更大更靠后。
         */
        System.out.println(s.findItinerary(Arrays.asList(
                Arrays.asList("JFK", "SFO"),
                Arrays.asList("JFK", "ATL"),
                Arrays.asList("SFO", "ATL"),
                Arrays.asList("ATL", "JFK"),
                Arrays.asList("ATL", "SFO"))));
    }

}